//
//  VectorTests.swift
//  AlgorithmsTests
//
//  Created by Archer on 2018/8/5.
//  Copyright © 2018年 Archer. All rights reserved.
//

import XCTest
@testable import SwiftyDSA

class VectorTests: XCTestCase {

    func recursive(_ from: Int, _ to: Int) {
        if to - from < 2 { return }
        let mid = (from + to) / 2
        print("will call from \(from)-mid \(mid)")
        recursive(from, mid)
        print("will call mid \(mid)-to \(to)")
        recursive(mid, to)
        print("recursive end")
    }
    
    func testRecursive() {
        recursive(0, 6)
    }
    
    
    /// Vector test
    func testEmpty() {
        let v = Vector<Int>()
        XCTAssertTrue(v.isEmpty)
        XCTAssertTrue(v.count == 0)
        XCTAssertEqual(v.first, nil)
        XCTAssertEqual(v.last, nil)
    }
    
    func testMakeEmpty() {
        let v = Vector<Int>()
        v.insert(10)
        XCTAssertFalse(v.isEmpty)
        XCTAssertTrue(v.count == 1)
        XCTAssertEqual(v.first, 10)
        XCTAssertEqual(v.last, 10)
        
        v.remove(at: 0)
        XCTAssertTrue(v.isEmpty)
        XCTAssertTrue(v.count == 0)
        XCTAssertEqual(v.first, nil)
        XCTAssertEqual(v.last, nil)
    }
    
    func testExpressibleByArrayLiteral() {
        let v: Vector = [5, 4, 6, 7]
        XCTAssertEqual(v.count, 4)
        XCTAssertEqual(v.first, 5)
        XCTAssertEqual(v.last, 7)
        XCTAssertEqual(v.endIndex, 4)
        
        v.removeLast()
        XCTAssertEqual(v.count, 3)
        XCTAssertEqual(v.last, 6)
    }
    
    func testInitWithOtherVector() {
        let other: Vector = [5, 4, 6, 7]
        let v = Vector(other)
        XCTAssertEqual(v.count, 4)
        XCTAssertEqual(v.first, 5)
        XCTAssertEqual(v.last, 7)
        XCTAssertEqual(v.endIndex, 4)
        
        v.removeLast()
        XCTAssertEqual(v.count, 3)
        XCTAssertEqual(v.last, 6)
    }
    
    func testInsert() {
        let v = Vector<Int>()
        v.insert(10)
        v.insert(9, at: 0)
        XCTAssertEqual(v.first, 9)
        XCTAssertEqual(v.last, 10)
        XCTAssertEqual(v.count, 2)
        
        v.insert(contentsOf: [11, 12], at: v.endIndex)
        XCTAssertEqual(v.last, 12)
        XCTAssertEqual(v.count, 4)
        XCTAssertEqual(v[2], 11)
    }
    
    func testRemove() {
        let v: Vector = [5, 4, 6, 7]
        v.removeLast()
        XCTAssertEqual(v.first, 5)
        XCTAssertEqual(v.last, 6)
        XCTAssertEqual(v.count, 3)
        
        v.removeFirst()
        XCTAssertEqual(v.first, 4)
        XCTAssertEqual(v.last, 6)
        XCTAssertEqual(v.count, 2)
        
        v.remove(at: 1)
        XCTAssertEqual(v.first, 4)
        XCTAssertEqual(v.last, 4)
        XCTAssertEqual(v.count, 1)
        
        v.insert(9)
        v.insert(10)
        v.removeAll()
        XCTAssertEqual(v.first, nil)
        XCTAssertEqual(v.last, nil)
        XCTAssertEqual(v.count, 0)
    }
    
    func testDisordered() {
        let v = Vector<Int>()
        for i in 0..<15 {
            v.insert(i)
        }
        XCTAssertEqual(v.disordered(), 0)
        
        v.removeAll()

        for i in (0..<15).reversed() {
            v.insert(i)
        }
        XCTAssertEqual(v.disordered(), 14)
        
        v.remove(at: 2...4)
        XCTAssertEqual(v.disordered(), 11)
        XCTAssertEqual(v.count, 12)
        XCTAssertEqual(v[2], 9)
    }
    
    func testFind() {
        let v = Vector<Int>()
        for _ in 0..<100 {
            v.insert(Int(arc4random_uniform(10000)))
        }
        XCTAssertEqual(v.find(v[50]), 50)
        XCTAssertEqual(v.find(v[38]), 38)
        XCTAssertEqual(v.find(v[99]), 99)
        
        v.insert(99999, at: 34)
        XCTAssertEqual(v.find(99999), 34)

        v.remove(at: 34)
        XCTAssertEqual(v.find(99999), -1)
    }
    
    func testSearch() {
        let v = Vector<Int>()
        for i in 0..<15 {
            v.insert(i)
        }
        for i in 0..<15 {
            XCTAssertEqual(v._search(i, from: 0, to: 15), i)
        }
        
        XCTAssertEqual(v._search(16, from: 0, to: 15), 14)
        XCTAssertEqual(v._search(-1, from: 0, to: 15), -1)
    }
    
    func testDeduplicate() {
        for _ in 0..<3 {
            var totalCount = 0
            let v = Vector<Int>()
            for _ in 0..<15 {
                var times = Int(arc4random_uniform(10) + 1) // 5
                let e = times
                if v.find(e) == NotFound {
                    totalCount += (times - 1)
                    while times > 0  {
                        
                        v.insert(e)
                        times -= 1
                    }
                }
            }
            print("vector = \(v)")
            XCTAssertEqual(v.deduplicate(), totalCount)
            print("vector = \(v)")
        }
        
        // 随机出现
        let v: Vector = [0, 1, 1, 9, 8, 7, 9, 8, 7, 6, 5, 4, 4, 5, 6, 6, 6, 0]
        XCTAssertEqual(v.deduplicate(), 10)
    }
    
    func testUniquify() {
        for _ in 0..<3 {
            var totalCount = 0
            let v = Vector<Int>()
            for i in 0..<15 {
                var times = Int(arc4random_uniform(10))
                if times > 0 {
                    totalCount += (times - 1)
                }
                while times > 0 {
                    v.insert(i)
                    times -= 1
                }
            }
            print("vector = \(v)")
            XCTAssertEqual(v.uniquify(), totalCount)
            print("vector = \(v)")
        }
    }
    
    func testSort() {
        for _ in 0..<5 {
            let v = Vector<Int>()
            for _ in 0..<1000 {
                v.insert(Int(arc4random_uniform(10000)))
            }
            DSABenchmark({
                v.sort()
            }) { (costs) in
                print("耗时 = \(costs)")
            }
            XCTAssertEqual(v.disordered(), 0)
        }
    }
    
    func testReverse() {
        let v0 = Vector<Int>()
        v0.reverse()
        print("v0 = \(v0)")
        
        let v1: Vector = [0]
        v1.reverse()
        print("v1 = \(v1)")
        
        let v2: Vector = [0, 1]
        v2.reverse()
        print("v2 = \(v2)")
        
        let v3: Vector = [0, 1, 2]
        v3.reverse()
        print("v3 = \(v3)")
        
        let v4: Vector = [0, 1, 2, 3]
        v4.reverse()
        print("v4 = \(v4)")
        
        let v5: Vector = [0, 1, 2, 3, 4]
        v5.reverse()
        print("v5 = \(v5)")
        
        let v6: Vector = [0, 1, 2, 3, 4, 5]
        v6.reverse()
        print("v6 = \(v6)")
    }
    
}
